package cs561.hao;

public class Alpha_beta_pruning_test // show leaf node, succeed!
{
	
	public static void print_utility(TreeNode _node)
	{
		System.out.println(_node.utility + " ");
	}
	
	public static void DFS(TreeNode _node) 
	{
		if (_node.leaf == true)
		{
			//print_utility(_node);
			System.out.println("Leaf node!");
		}
		else
		{
			for(int i = 0; i < _node.childrenList.size(); i++)
			{
				//System.out.println("ChildrenList.size() = " + _node.childrenList.size());
				System.out.print(_node.nodeName + ": ");
				print_utility(_node);
				
				System.out.print(_node.childrenList.get(i).nodeName + ": ");
				print_utility(_node.childrenList.get(i));
				DFS(_node.childrenList.get(i));
			}		
			
/*			for(int i = 0; i < _node.childrenList.size(); i++)
			{
				print_utility(_node.childrenList.get(i));
			}*/
		}
	}
	
	public static int abp(TreeNode _node, int _depth, int _alpha, int _beta, int _player)//? not int _node.alpha,?
	{
		if ((_depth == 0) || (_node.leaf == true ))
		{
			System.out.println(_node.nodeName + " is bottom node: " + _node.utility);
			return _node.utility;
		}
		else if(_player == 1)
		{
			_node.alpha = _alpha;
			_node.beta = _beta;
			
			for(int i = 0; i < _node.childrenList.size(); i++)
			{
				_node.alpha = Math.max(_node.alpha, abp(_node.childrenList.get(i), _depth--, _node.alpha, _node.beta, -_player));
				if (_node.alpha >= _node.beta)
				{
					System.out.println(_node.nodeName + " pruned.");
					//_node.alpha = Integer.MAX_VALUE;//?
					//_node.alpha = 99;
					break;
				}
				
			}
			System.out.println(_node.nodeName + " " + _node.alpha);
			return _node.alpha;
		}
		else
		{
			_node.alpha = _alpha;
			_node.beta = _beta;
			
			for(int i = 0; i < _node.childrenList.size(); i++)
			{
				_node.beta = Math.min(_node.beta, abp(_node.childrenList.get(i), _depth--, _node.alpha, _node.beta, -_player));
				if (_node.alpha >= _node.beta)
				{
					System.out.println(_node.nodeName + " pruned.");
					//_node.beta = Integer.MIN_VALUE;//?
					//_node.beta = -99;//?
					break;
				}
				
			}
			System.out.println(_node.nodeName + " " + _node.beta);
			return _node.beta;// ? after finish node4,5 than return?
		}
	}
	
	public static void main(String[] args)
	{
		/*
		//construct treeA
		TreeNode_test node_a = new TreeNode_test();
		node_a.root = true;
		node_a.nodeName = "node_a";
		node_a.utility = 1;
		
		TreeNode_test node_b = new TreeNode_test();
		node_b.utility = 2;
		node_b.nodeName = "node_b";
		
		TreeNode_test node_c = new TreeNode_test();
		node_c.utility = 3;
		node_c.nodeName = "node_c";
		
		TreeNode_test node_d = new TreeNode_test();
		node_d.utility = 4;
		node_d.nodeName = "node_d";
		
		TreeNode_test node_e = new TreeNode_test();
		node_e.utility = 5;
		node_e.nodeName = "node_e";
		
		TreeNode_test node_f = new TreeNode_test();
		node_f.utility = 6;
		node_f.nodeName = "node_f";
		
		TreeNode_test node_g = new TreeNode_test();
		node_g.utility = 7;
		node_g.nodeName = "node_g";
		
		TreeNode_test node_h = new TreeNode_test();
		node_h.utility = 8;
		node_h.nodeName = "node_h";
		
		//depth 0.
		node_a.addChild(node_b);
		node_a.addChild(node_c);
		node_a.addChild(node_d);
		
		//depth 1.
		node_b.addChild(node_e);
		node_b.addChild(node_f);
		
		node_c.addChild(node_g);
		
		node_d.addChild(node_h);
		
		//print_utility(node_a);
		//print_utility(node_g);
		//end of treeA
		*/
		
		/*
		//construct treeB
		TreeNode_test node_a = new TreeNode_test();
		node_a.root = true;
		node_a.nodeName = "node_a";
		node_a.utility = 1;
		
		TreeNode_test node_b = new TreeNode_test();
		node_b.utility = 2;
		node_b.nodeName = "node_b";
		
		TreeNode_test node_c = new TreeNode_test();
		node_c.utility = 3;
		node_c.nodeName = "node_c";
		
		TreeNode_test node_d = new TreeNode_test();
		node_d.utility = 4;
		node_d.nodeName = "node_d";
		
		TreeNode_test node_e = new TreeNode_test();
		node_e.utility = 5;
		node_e.nodeName = "node_e";
		
		TreeNode_test node_f = new TreeNode_test();
		node_f.utility = 6;
		node_f.nodeName = "node_f";
		
		TreeNode_test node_g = new TreeNode_test();
		node_g.utility = 7;
		node_g.nodeName = "node_g";
		
		TreeNode_test node_h = new TreeNode_test();
		node_h.utility = 8;
		node_h.nodeName = "node_h";
		
		TreeNode_test node_i = new TreeNode_test();
		node_i.utility = 9;
		node_i.nodeName = "node_i";
		
		TreeNode_test node_j = new TreeNode_test();
		node_j.utility = 10;
		node_j.nodeName = "node_j";
		//depth 0
		node_a.addChild(node_b);
		node_a.addChild(node_c);
		
		//depth 1
		node_b.addChild(node_d);
		node_b.addChild(node_e);
		
		node_c.addChild(node_f);
		
		//depth 2
		node_d.addChild(node_g);
		
		node_f.addChild(node_h);
		
		//depth 3
		node_g.addChild(node_i);
		node_g.addChild(node_j);
		
		//System.out.println(node_a.nodeName);
		DFS(node_a);
		//DFS(node_b);
		//DFS(node_c);
		//DFS(node_d);
		//DFS(node_e);
		
		//print_utility(node_b.childrenList.get(1));
		//System.out.println(node_a.childrenList.size());
		//end of treeB
		*/
				
		/*	 
		//build treeE
		TreeNode_test node_01 = new TreeNode_test();
		node_01.root = true;
		node_01.nodeName = "node_01";
		//node_01.alpha = Integer.MIN_VALUE;
		//node_01.beta = Integer.MAX_VALUE;
		
		TreeNode_test node_02 = new TreeNode_test();
		node_02.nodeName = "node_02";
		
		TreeNode_test node_03 = new TreeNode_test();
		node_03.nodeName = "node_03";
		
		TreeNode_test node_04 = new TreeNode_test();
		node_04.nodeName = "node_04";
		node_04.utility = 7;
		
		TreeNode_test node_05 = new TreeNode_test();
		node_05.nodeName = "node_05";
		node_05.utility = 6;
		
		TreeNode_test node_06 = new TreeNode_test();
		node_06.nodeName = "node_06";
		node_06.utility = 5;
		
		TreeNode_test node_07 = new TreeNode_test();
		node_07.nodeName = "node_07";
		node_07.utility = 4;
		
		TreeNode_test node_08 = new TreeNode_test();
		node_08.nodeName = "node_08";
		node_08.utility = 9;
		
		//depth 0;
		node_01.addChild(node_02);
		node_01.addChild(node_03);
		node_01.addChild(node_08);
		
		//depth 1;
		node_02.addChild(node_04);
		node_02.addChild(node_05);
		
		node_03.addChild(node_06);
		node_03.addChild(node_07);
		
		//DFS(node_01);
		int result = abp(node_01, 2, Integer.MIN_VALUE, Integer.MAX_VALUE, 1);
		System.out.println(result);//end of treeE
		*/
		
		//build treeD
		TreeNode node_01 = new TreeNode();
		node_01.root = true;
		node_01.nodeName = "node_01";
		//node_01.utility = 0;
		
		TreeNode node_02 = new TreeNode();
		node_02.nodeName = "node_02";
		//node_02.utility = 0;
		
		TreeNode node_03 = new TreeNode();
		node_03.nodeName = "node_03";
		//node_03.utility = 0;
		
		TreeNode node_04 = new TreeNode();
		node_04.nodeName = "node_04";
		//node_04.utility = 0;
		
		TreeNode node_05 = new TreeNode();
		node_05.nodeName = "node_05";
		//node_05.utility = 0;
		
		TreeNode node_06 = new TreeNode();
		node_06.nodeName = "node_06";
		//node_06.utility = 0;
		
		TreeNode node_07 = new TreeNode();
		node_07.nodeName = "node_07";
		node_07.utility = 3;
		
		TreeNode node_08 = new TreeNode();
		node_08.nodeName = "node_08";
		//node_08.utility = 0;
		
		TreeNode node_09 = new TreeNode();
		node_09.nodeName = "node_09";
		//node_09.utility = 0;
		
		TreeNode node_10 = new TreeNode();
		node_10.nodeName = "node_10";
		//node_10.utility = 0;
		
		TreeNode node_11 = new TreeNode();
		node_11.nodeName = "node_11";
		//node_11.utility = 0;
		
		TreeNode node_12 = new TreeNode();
		node_12.nodeName = "node_12";
		//node_12.utility = 0;
		
		TreeNode node_13 = new TreeNode();
		node_13.nodeName = "node_13";
		//node_13.utility = 0;
		
		TreeNode node_14 = new TreeNode();
		node_14.nodeName = "node_14";
		//node_14.utility = 0;
		
		TreeNode node_15 = new TreeNode();
		node_15.nodeName = "node_15";
		//node_15.utility = 0;
		
		TreeNode node_16 = new TreeNode();
		node_16.nodeName = "node_16";
		//node_16.utility = 0;
		
		TreeNode node_17 = new TreeNode();
		node_17.nodeName = "node_17";
		node_17.utility = 7;
		
		TreeNode node_18 = new TreeNode();
		node_18.nodeName = "node_18";
		//node_18.utility = 0;
		
		TreeNode node_19 = new TreeNode();
		node_19.nodeName = "node_19";
		//node_19.utility = 0;
		
		TreeNode node_20 = new TreeNode();
		node_20.nodeName = "node_20";
		//node_20.utility = 0;
		
		TreeNode node_21 = new TreeNode();
		node_21.nodeName = "node_21";
		//node_21.utility = 0;
		
		TreeNode node_22 = new TreeNode();
		node_22.nodeName = "node_22";
		node_22.utility = 10;
		
		TreeNode node_23 = new TreeNode();
		node_23.nodeName = "node_23";
		node_23.utility = 15;
		
		TreeNode node_24 = new TreeNode();
		node_24.nodeName = "node_24";
		node_24.utility = 13;
		
		TreeNode node_25 = new TreeNode();
		node_25.nodeName = "node_25";
		node_25.utility = 7;
		
		TreeNode node_26 = new TreeNode();
		node_26.nodeName = "node_26";
		node_26.utility = 100;
		
		TreeNode node_27 = new TreeNode();
		node_27.nodeName = "node_27";
		node_27.utility = 20;
		
		TreeNode node_28 = new TreeNode();
		node_28.nodeName = "node_28";
		node_28.utility = 11;
		
		TreeNode node_29 = new TreeNode();
		node_29.nodeName = "node_29";
		node_29.utility = 5;
		
		TreeNode node_30 = new TreeNode();
		node_30.nodeName = "node_30";
		node_30.utility = 4;
		
		TreeNode node_31 = new TreeNode();
		node_31.nodeName = "node_31";
		node_31.utility = 70;
		
		TreeNode node_32 = new TreeNode();
		node_32.nodeName = "node_32";
		node_32.utility = 6;
		
		TreeNode node_33 = new TreeNode();
		node_33.nodeName = "node_33";
		node_33.utility = 2;
		
		TreeNode node_34 = new TreeNode();
		node_34.nodeName = "node_34";
		node_34.utility = 17;
		
		TreeNode node_35 = new TreeNode();
		node_35.nodeName = "node_35";
		node_35.utility = 1;
		
		TreeNode node_36 = new TreeNode();
		node_36.nodeName = "node_36";
		node_36.utility = 20;
		
		TreeNode node_37 = new TreeNode();
		node_37.nodeName = "node_37";
		node_37.utility = 50;
		
		//depth 0
		node_01.addChild(node_02);
		node_01.addChild(node_03);
		node_01.addChild(node_04);
		
		//depth 1
		node_02.addChild(node_05);
		node_02.addChild(node_06);
		node_02.addChild(node_07);
		
		node_03.addChild(node_08);
		node_03.addChild(node_09);
		
		node_04.addChild(node_10);
		node_04.addChild(node_11);
		
		//depth 2
		node_05.addChild(node_12);
		node_05.addChild(node_13);
		node_05.addChild(node_14);
		
		node_06.addChild(node_15);
		node_06.addChild(node_16);
		
		node_08.addChild(node_17);
		node_08.addChild(node_18);
		
		node_09.addChild(node_19);
		
		node_10.addChild(node_20);
		
		node_11.addChild(node_21);
		
		//depth 3
		node_12.addChild(node_22);
		node_12.addChild(node_23);
		node_12.addChild(node_24);
		
		node_13.addChild(node_25);
		node_13.addChild(node_26);
		
		node_14.addChild(node_27);
		
		node_15.addChild(node_28);
		node_15.addChild(node_29);
		
		node_16.addChild(node_30);
		node_16.addChild(node_31);
		
		node_18.addChild(node_32);
		
		node_19.addChild(node_33);
		node_19.addChild(node_34);
		
		node_20.addChild(node_35);
		node_20.addChild(node_36);
		
		node_21.addChild(node_37);
		
		//DFS(node_01);// test, succeed!
		int result = abp(node_01, 4, Integer.MIN_VALUE, Integer.MAX_VALUE, 1);
		//int result = abp(node_12, 1, Integer.MIN_VALUE, Integer.MAX_VALUE, -1);
		System.out.println("MAX: " + result);
		
		//end of treeD;
	
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
	}// end main	
	
	
}
